#!/usr/bin/python
# Write Python 3 code in this online editor and run it.
'''
插入排序：
对于前i-1个数已经有序的情况下，将第i个数插入到合适的位置
首先将第二个元素和第一个元素进行比较，如果第二个元素小于第一个元素，
则将第一个元素向后移动，且第二个元素执行插入，即前两个元素有序
进行第二轮比较，将第三个元素依次与第二和第一元素比较，
并将第三个元素插入合适位置

需要对n-1个数据进行插入
'''

def InsertionSort(a):
	n = len(a)
	for i in range(1,n):
		x = a[i]
		j = i - 1
		while j >= 0:
			if x < a[j]:
				a[j+1] = a[j]
				j -= 1
			else:
				break
		a[j+1] = x
		print(a)
		
a = [8,7,6,5,4,3,2,1]  #
InsertionSort(a)
